﻿// 0817train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <stack>

using namespace std;

/*
  实现一个模拟目录管理功能的软件，输入一个命令序列，输出最后一条命令运行结果。
 支持命令： 
1) 创建目录命令：mkdir 目录名称，如mkdir abc为在当前目录创建abc目录，
如果已存在同名目录则不执行任何操作。
此命令无输出。

2) 进入目录命令：cd 目录名称，如cd abc为进入abc目录，
特别地，cd ..为返回上级目录，如果目录不存在则不执行任何操作。此命令无输出。

3) 查看当前所在路径命令：pwd，输出当前路径字符串

约束:
1) 目录名称仅支持小写字母；mkdir和cd命令的参数仅支持单个目录，
如mkdir abc和cd abc;不支持嵌套路径和绝对路径，
如mkdir abc/efg，cd abc/efq是不支持的。
2) 目录符号为/，根目录/作为初始目录。
3) 任何不符合上述定义的无效命令不做任何处理并且无输出。

输入描述
输入N行字符串，每一行字符串是一条命令

输出描述
输出最后一条命令运行结果字符串

输入
mkdir abc
cd abc
pwd
输出
/abc/

 */

/*
 mkdir的时候，拼接stack里的字符，存入path_map
 cd的时候，拼接stack里的字符，查找set
 */
class Solution01
{
public:
    struct Node01
    {
        string name;
        unordered_set<string>next_path_set;

        void addNewPath(string&new_path)
        {
            next_path_set.insert(new_path);
        }

        Node01() = default;
        Node01(string name) :name(name) {};
    };
    unordered_map<string, Node01>path_map;
    vector<string>path_stack;

    string getCurrPath()
    {
        if (path_stack.size() == 1) return "/";

        string curr_path;
        for (int i=0; i<path_stack.size();i++)
        {
            string path_str = path_stack[i];
            curr_path += path_str;
            if (i!=0)
            {
                curr_path += '/';
            }
        }
        return curr_path;
    }

    bool checkLowcase(string&oh_str)
    {
        for (auto&oh_char:oh_str)
        {
            bool is_lowcase = oh_char >= 'a' && oh_char <= 'z';
            if (!is_lowcase) return false;
        }
        return true;
    }

    bool checkVerify(vector<string>&order_vec, string& order_str)
    {
        /*
        mkdir abc
		cd abc
		pwd
         */
        if (order_vec[0]=="mkdir")
        {
            if (!checkLowcase(order_vec[1])) return false;

            return true;
        }
        else if (order_vec[0] == "cd")
        {
            if (order_vec[1] == "..") return true;
            if (!checkLowcase(order_vec[1])) return false;
            return true;
        }
        else if (order_vec[0] == "pwd")
        {
            if (order_str != "pwd") return false;
            return true;
        }
        return false;
        //checkVerify
    }

    void handleOrder(string&order_str, bool is_end)
    {
        vector<string>order_vec;
        stringstream oh_sstream(order_str);
        string token;
        while (oh_sstream>>token)
        {
            order_vec.push_back(token);
        }

        if (!checkVerify(order_vec, order_str)) return;

        if (order_vec[0]=="mkdir")
        {
            string curr_path = getCurrPath();
            string new_path_key = curr_path + order_vec[1] +"/";
            if (path_map.count(new_path_key)==0)
            {
                Node01 path_node(new_path_key);
                path_map[new_path_key] = path_node;

                path_map[curr_path].addNewPath(new_path_key);
            }
			    
        }
        else if (order_vec[0] == "cd")
        {
            if (order_vec[1]==".." && path_stack.size()>1)
            {
                path_stack.pop_back();
                return;
            }

            string curr_path = getCurrPath();
            string next_path = curr_path + order_vec[1] + "/";

            if (path_map[curr_path].next_path_set.count(next_path)>0)
            {
                path_stack.push_back(order_vec[1]);
            }
            //cout << getCurrPath();
        }
        else if (order_vec[0] == "pwd")
        {
            if (is_end)
            {
                cout << getCurrPath();
            }
	        
        }

        //handleOrder
    }

    void solve01(vector<string>&order_total_vec)
    {
        path_stack.push_back("/");
        Node01 root_path("/");
        path_map["/"] = root_path;

        int vec_size = order_total_vec.size();
        for (int i=0; i< vec_size; i++)
        {
            string order_str = order_total_vec[i];
            bool is_end = i == vec_size - 1;
            handleOrder(order_str, is_end);
        }
	    
    }

};

/*
mkdir test
cd test
mkdir test
cd ..
mkdir test
pwd
 */


/*
 给定一个候选人编号的集合 candidates 和一个目标数 target ，
 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
 */
class Solution02 {
public:
    int track_sum = 0;
    int track_target;
    vector<int>sub_vec;
    vector<vector<int>>result_vec;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        track_target = target;
        backTrack(candidates, 0);
        return result_vec;
    }

    void backTrack(vector<int>&origin_vec, int start)
    {
        if (track_sum == track_target)
        {
            result_vec.push_back(sub_vec);
        }

        if (track_sum > track_target)
        {
            return;
        }

        for (int i=start; i<origin_vec.size(); i++)
        {
            if (i > start && origin_vec[i] == origin_vec[i - 1]) continue;

            //做选择
            track_sum += origin_vec[i];
            sub_vec.push_back(origin_vec[i]);
            //回溯
            backTrack(origin_vec, i + 1);
            //撤销选择
            track_sum -= origin_vec[i];
            sub_vec.pop_back();
        }

	    //backTrack
    }
};


/*
 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
 */

class Solution03 {
public:
    vector<int>track_vec;
    vector<vector<int>>result_vec;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        //排序，方便backTrack剪枝去重
        sort(nums.begin(), nums.end());
        int vec_size = nums.size();
        vector<bool>used_vec(vec_size);
        backTrack(nums, used_vec);
        return result_vec;
    }


    void backTrack(vector<int>&nums, vector<bool>&used_vec)
    {
        if (track_vec.size()==nums.size())
        {
            result_vec.push_back(track_vec);
            return;
        }

        for (int i=0; i<nums.size(); i++)
        {
            if (used_vec[i])
                continue;

            //剪枝，去除重复情况
            if (i > 0 && nums[i] == nums[i - 1] && !used_vec[i - 1])
                continue;

            //做选择
            track_vec.push_back(nums[i]);
            used_vec[i] = true;
            //回溯
            backTrack(nums, used_vec);
            //撤销选择
            track_vec.pop_back();
            used_vec[i] = false;
        }
    }
};

/*
 示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
 */
class Solution04 {
public:
    int track_target;
    int track_sum = 0;
    vector<int>track_vec;
    vector<vector<int>>result_vec;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        track_target = target;
        backTrack(candidates, 0);
        return result_vec;
    }

    void backTrack(vector<int>&origin_vec, int start)
    {
        if (track_sum == track_target)
        {
            result_vec.push_back(track_vec);
        }

        if (track_sum>track_target)
        {
            return;
        }

        for (int i=start; i<origin_vec.size(); i++)
        {
			//做选择
            track_sum += origin_vec[i];
            track_vec.push_back(origin_vec[i]);
			//回溯
            backTrack(origin_vec, i);
			//撤销选择
            track_sum -= origin_vec[i];
            track_vec.pop_back();
        }
    }
};

int main()
{
	{
        //candidates = [2,3,6,7], target = 7
        vector<int>candidates = { 2,3,6,7 };
        int target = 7;
        Solution04 solu;
        vector<vector<int>>result_vec = solu.combinationSum(candidates, target);

        cout << result_vec.size();

        return 0;
	}
	{
        //输入：nums = [1,1,2]
        vector<int>nums = { 1,1,2 };
        Solution03 solu;
        vector<vector<int>>result = solu.permuteUnique(nums);
        cout << result.size();

        return 0;
	}
	{
        //candidates = [10,1,2,7,6,1,5], target = 8,
        vector<int>candidates = { 10,1,2,7,6,1,5 };
        int target = 8;
        Solution02 solu;
        vector<vector<int>>result = solu.combinationSum2(candidates, target);
        //for (auto&mini_vec:result)
        //{
        //    for (auto&num:mini_vec)
        //    {
        //        cout << num << ' ';
        //    }
        //    cout << '\n';
        //}

        cout << result.size();
        return 0;
	}
    //vector<string>order_total_vec;
    //string input;
    //while (getline(cin,input))
    //{
    //    if (input.empty()) break;
    //    order_total_vec.push_back(input);
    //}

    vector<string>order_total_vec = {"mkdir test","cd test","mkdir test",
    	"cd ..","mkdir test","pwd"};
    //vector<string>order_total_vec = { "mkdir abc","cd abc", "mkdir abc","cd abc","pwd" };
    Solution01 solu;
    solu.solve01(order_total_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
